Data communication between computers and/or terminals is frequently required in computer systems. For example, "dumb terminals" must often be connected to mainframes, or microcomputers must be interconnected. Improving the efficiency of data transmission between such devices is the field of the present invention.
The majority of data communications applications in use today transmit data in some form of bit serial format. This includes commonly used asynchronous serial data communication, such as that used between computers or terminals and modems, as well as computing devices and serial printers. The end to end format on many data communications calls between modems on the public switched telephone network is simply asynchronous serial data, end to end.
Today, many data communications links are accomplished using communications protocols employing data packets or packetized data. For example, most long distance calls to remote mainframe computers by individuals wishing to interrogate those computers are accomplished through commercial packet switch networks such as Telenet and Tymnet. In the commercial packet switch networks, local nodes are maintained at many cities. An incoming call from a modem over a local telephone subscriber link will be received by a modem at the local node of the packet switch network operator. Information transmitted over this communication length is received by the node controller and used to set up a virtual circuit within the packet switch network. For example, if a user in Atlanta is trying to communicate with a mainframe computer in San Francisco, the Atlanta user will call the local office of the commercial packet switch network. The local user transmits the information identifying the computer he or she wishes to contact in California. The packet switch network operator will, under most circumstances, already have a physical link established between Atlanta and San Francisco over which data is flowing. The node controller sets up a virtual connection between the modem upon which it is receiving the Atlanta subscriber's call and forwards this information to its San Francisco node which establishes the physical link between one of its local modems and the mainframe computer and acknowledges the existence of the virtual circuit. The virtual circuit is simply a logical connection between the modem at the Atlanta node and the modem at the San Francisco node of which both controllers are aware. Data received at the Atlanta node from the caller is assembled into packets of data which include header information identifying the virtual circuit, and the physical modem at the San Francisco node to which the data within the packet should be routed. A similar process takes place for data transmitted back from the computer in San Francisco to the user in Atlanta. In this way, a single physical link between Atlanta and San Francisco can be used to handle multiple data communications calls in an efficient manner.
Recommendation X.25 of the International Consultative Committee on Telephony and Telegraphy (CCITT) is a commonly used protocol for packet switched networks. Many modern intelligent modems, including the V series modems in effect by Hayes Microcomputer Products Inc. of Norcross, Ga., the assignee of the present invention, internally include the capability to handle X.25 calls. Thus, the modems can be provided data from multiple sources and have the capability of adding appropriate information identifying the virtual connection at the transmission end and receiving and decoding same at the receiving end in order to effect multiple virtual circuits over a single physical link between two such modems. In these cases, the data is packetized according to the protocol specified in CCITT recommendation X.25.
The International Standards Organization has defined a standard model for communication of data between and among computers and other devices. The model conceptually divides certain aspects of data communications under different layers and establishes rules for how communication of information is passed back and forth through the layers. As known to those skilled in the art, there are many applications in which collection of data is made from one layer past, according to a predetermined protocol, onto another layer, often with additional information added to the data as it is passed down to a lower layer. Thus, packets of data may be assembled at certain layers and later strung together to form a "packet of packets" as information is passed on to the next layer.
Another common application of rudimentary packetizing is found in modem error correcting intelligent modems, such as those meeting recommendation V.42 bis of the CCITT. In these modems, link access protocol M (lapM) is used to assemble small packets or frames of data which are then transmitted together as a group. The packet includes information, such as check sums, which allows the receiving modem to ascertain if an error was made in transmitting the data. If an error is detected in a given packet the remote terminal will transmit a request that the packet be resent.
It is also known to those skilled in the art that most all local area networks (LANs) used today employ some form of fixed or variable length packets when transmitting data between and among nodes on the network. Since a local area network, by its nature, requires that the various nodes be addressable in some fashion, data sent between devices is packetized and includes address headers etc., according to the protocol defining the local area network.
A packet of data is a variable number of data characters strung together to be transmitted in contiguous fashion. The data packet contains a header which proceeds the data in the packet, the data, and a footer which follows the data. The header and footer contain information, such as the number of characters in the packet, the origin and destination addresses, and error detection and correction information, which enables the receiving device to determine if the transmission was error free and where the information should go.
Whenever any data is transmitted in a packet, the packet contains a header and footer that constitute overhead for the end to end data link. Thus, if ten characters of data are transmitted in ten individual packets, these overhead bits are transmitted ten times. In contrast, if the ten characters of data are put into a single packet, the overhead bits are only transmitted once. Thus, packetizing into larger packets reduces transmission of overhead bits, which allows more data to be transmitted over the network, thereby increasing system throughput and reducing system congestion.
Of course, the above described reduction in overhead has a cost. Specifically, there is a latency delay between the time when the first characters are received by the packet assembler and the time when the data packet is transmitted. This latency delay is attributable to the delay required for accumulating data characters to form a packet. As an illustration, a packet assembler might only form a packet when ten data characters are ready to be transmitted. The packet assembler may get nine characters in fast, contiguous fashion, but then have to wait a long time to receive the tenth character. This delay incurred by waiting for the tenth character slows down communication between the user and the destination terminal.
Problems with latency delay arise principally when a terminal user is communicating with an application or interrogating the database of the mainframe through a communication link that packetizes data. This arises most commonly in communications with remote mainframes via commercial packet switch carriers while running applications on local area networks. Additionally, it can also arise when a dedicated physical link is used but the data is packetized for purposes of implementing error detection and correction.
The problem with the latency delay principally arises from the fact that most remote systems still display an indication of the typed characters on the user's terminal screen via Equiplex. Equiplex is a commonly used system in which the user will type a character intended for the remote Computing system. The character makes its way through the communication link and is processed by the remote mainframe application. The application then echoes the character back to the local terminal by sending it back for display on the terminal screen. This was originally conceived as a crude form of error detection in that many errors which took place in transmission from terminal to remote device would not be corrected on the return trip and an erroneous character would appear on the user's screen or teletype paper. It remains in use today.
If there is a large latency delay, the user has the experience of typing on the keyboard with "nothing happening." In other words, the user types but sees nothing on the screen in the way of visual feedback to indicate that his or her efforts are being received by the remote system. Inexperienced users not familiar with latency delays may start typing keys repetitively under such circumstances. When the packet is assembled and transmitted, and the return packet makes it way through the network with the echoed characters, a burst of data appears on the screen.
Thus, it is desirable to minimize latency delays to avoid user dissatisfaction and frustration. As described hereinabove, overly zealous minimizing of latency delays can lead to inefficient use of the data transmission capability of a network by sending small packets that have a high ratio of overhead bits to message bits leading to general degradation of throughput over the data communications link.
The inventors of the present invention have identified transmission of small data packets as particularly problematic in many practical local area network installations. Overall network throughput for all users is degraded seriously when one or more devices commence frequent transmission of small packets of data. The overall efficiency of the network is reduced and all users experience the network slowing down under such circumstances. A network modem that is connected directly to a local area network and onto the telephone line is a node thereon, and is an example of a device for which it is highly desirable to minimize latency delays since many common uses of a modem involve individuals sitting at terminal devices typing data and waiting for echoed characters to appear on the screen. At the same time, the slowed transmission of data often encountered in modems (vis-a-vis network bit rates) can lead to generating small inefficient packets which reduce overall message information throughput and slow down the network. It is in this environment in which the inventors of the present invention believe it will have some of its greatest utility.
Most packet assemblers do not use packet size as the sole criteria for packet assembly and transmission precisely because the unpredictable asynchronous data provided to the modem causes long delays in accumulating a packet. Many packet assemblers, therefore, use a timer to define and limit packet assembly. The timer detects asynchronous serial data characters entering the packet assembler/disassembler (PAD) from a terminal or other serial data source, and when no data enters the PAD for a pre-determined period of time a time-out signal is generated. The time-out signal triggers packeting and transmission of a packet. Thus, delays inherent in waiting for character accumulation are limited to the "time-out period."
In the ten character transmission example given earlier, the packet assembler with a timer would transmit the first nine characters as a packet if the tenth character did not arrive before the timer ran out. The tenth character would be transmitted in the subsequent packet of data. The delay normally incurred in waiting for the tenth data character is thereby shortened to what is called a "latency delay." The latency delay is equal to the time-out period.
It might seem that the time-out delay period should be very short so that data is transmitted with minimum delay. However, as discussed, systems such as the local area network (LAN) Ethernet have a multiple access topology with many users. In other words, many terminals communicate over the same network. Therefore, the systems require fast throughput of data between terminals or else the network becomes congested and file transfer performance is intolerably slow. Sending data packets too frequently causes other users access to the system to be reduced and system performance is degraded. By creating larger data packets, throughput time is decreased. To form these larger data packets, the time-out period is lengthened. However, lengthening the time-out period increases the latency delay, which reduces the terminal user's efficiency.
A fundamental problem with current packet assemblers is that the latency delay attributable to the timer is very long so that throughput can be increased by virtue of increased packet size. For instance, the time-out period is selected in increments of twentieths of a second in the communication protocol of CCITT Recommendation X.3. This long time-out helps to reduce system congestion, which is a serious problem on many local area networks, but latency delays become increasingly annoying.
Recently, some packet assemblers have been introduced that reduce latency delay. As is known to those skilled in the art, a number of modem error correcting modems will successively increase packet size upon commencement of transmission until either a predetermined or dynamically determined maximum packet size is reached. The ramp-up dynamic packet sizing system transmits consecutively larger packet sizes. For example, the first few packets transmitted increase in size from, for example, 8 characters to 16 characters to 32 characters etc. This expansion of packet size continues until a time-out occurs before a packet is transmitted. Subsequent packet transmissions again ramp-up from smaller to larger packet size. In this manner, latency delays for the first few characters are reduced. This ramping of packet size has been used in a number of intelligent modems which include error correcting capability. This type of system is particularly useful with devices such as modems where the end-to-end communication is often an interactive session between a user at a terminal and a host device at the other end. The is because, in this environment, requirement of a large number of characters in a packet would lead to the terminal user typing many characters prior to seeing any of them echoed back to his or her screen by a far end device running an echoplex protocol.
Another method of reducing latency delay is used in the CCITT Recommendation X.25 data communications protocol. The X.25 protocol uses a predetermined character recognition system to reduce latency delay. In this system, certain characters, such as a carriage return, are pre-programmed to be recognized by the packet assembler. Whenever one of the predetermined characters is encountered in the serial data stream, the packet assembler responds to the character as a designator of the end of a packet and assembles and transmits a packet immediately (CCITT X.3 .sctn. 1.4.3). The expedient of defining a predetermined character as terminated in the packet is also particularly useful in networks transmitting data in an interactive session between a user at a terminal and a remote host. For example, a user at a terminal making inquiries of a data base on a remote host normally types a line of data terminated by a carriage return in order to command the application running on the host to perform some task. Many such applications run on host computers will buffer received data until a carriage return character is received and then transfer the contents of the buffer to a command interpreter or the like in order to act on the received command. Thus, the use of a predetermined character as an indicator that the packet should be terminated and sent avoids latency delays in these circumstances.
However, if the packet assembler is part of a network that is transferring a file of binary data, assembling and transmitting the packet in response to receipt of a fixed "character" (i.e., a particular seven or eight bit pattern) can lead to reduced throughput as smaller packets are sent in response to receipt of the predetermined character. By assembling a packet and transmitting immediately when one of these predetermined characters is encountered, the latency delay inherent in waiting for the time-out signal is avoided altogether. These characters are thus used as "latency indicator signals."
The character identification system, however, still requires a priori knowledge of which characters precede a latency delay. The character identification system cannot dynamically recognize new latency indicating characters as they become apparent. Additionally, latency delays not following preidentified characters are not addressed at all.
Many currently popular file transfer protocols have characteristics of a fixed packet length and a required sequence of acknowledgement signals. For example, a number of protocols use an ACK/NACK acknowledgement sequence for a receiving device to acknowledge receipt of a packet of fixed length back to the device which sent it. Where communication is employed using such a protocol, the transmitting device will assemble and transmit a packet of fixed length. It will transmit no further data until it receives the appropriate acknowledgement from the far end device with which it is communicating. An acknowledgement signal indicates that the packet was successfully received and, to the extent that redundancy and error detection capability is included in the protocol, it was received without error. The other acknowledgement signal will indicate that a transmission error was detected. This is interpreted by the transmitting device to be a request to retransmit the last packet.
It should be remembered that such a protocol is often run end-to-end between devices which communicate through a packet switch network. In such an arrangement, the packet switch network needs to be as transparent as possible to the peculiarities of the protocol employed by the devices outside the packet switch network. When a fixed packet length ACK/NACK protocol is used, prior art packet assemblers were almost always left in a position of waiting for a time-out before the packet containing the Nth character would be forwarded to the far end device, where N is the fixed number of characters per packet. This is because the transmitting device will only send end characters until it is forced, by the rules of its protocol, to wait for the acknowledgement signal. The packet assembler is dutifully buffering up the characters waiting for what it considers to be a complete packet, or for some other event to occur which indicates that the packet should be transmitted. In most cases, this will be time-out and will thus introduce a latency delay. Once the packet is forwarded, the acknowledgement signal will be returned by the far end. Naturally, as this signal travels through the packet switch network, it is often left waiting for more characters which, under the rules of the protocol, do not come. Thus, the packet switch network is left holding only the acknowledgement character until a time-out occurs in the reverse channel which causes a high overhead, one character packet to be transmitted back to the first device. This process is then repeated.
As will be apparent from the foregoing description, the use of a fixed packet length acknowledgement based protocol on end-to-end devices, which are communicating through a network employing its own rules with respect to packet size and packet transmission often lead to a case where unnecessary and undesirable latency delays are introduced because a time-out must occur before either the last characters of a transmitted packet are sent and because a time-out is required in order to transmit the acknowledgement signal in the reverse channel.
Another means of reducing throughput time is shown in U.S. Pat. No. 4,680,773, issued to Amundson. In Amundson, packets are transmitted into a network. Whenever an error message is received from the network, the size of subsequently transmitted packets is reduced. Thus, because these smaller packets are more likely to be passed through the system error free, there is a reduction in throughput time because fewer data re-transmit requests occur. However, latency delays not associated with failed transmissions are not addressed. Thus, even in the Amundson patent the fundamental problem of latency delay remains.
A need yet exists for a method of avoiding the latency delay of time-out systems while not diminishing throughput performance.
There is a need to minimize latency delay in packet assemblers while not substantially decreasing system throughput. Thus, there is a need in the art for a packet assembler which can dynamically adapt to detected patterns in the data it is carrying in order to minimize latency delay, while, at the same time, not unduly sacrificing throughput. In particular, it is desirable to have a packet assembler for which the decision to forward a packet can be made based on criteria which are essentially independent of the end-to-end communications protocol in use. The present inventors have recognized that there is normally a fundamental tradeoff between latency delay and system throughput. Long latency delays are normally associated with larger packet sizes. The larger packet sizes make most efficient use of the network capacity by maximizing the ratio of data characters to overhead characters. As noted above, there are many applications in which latency delays are highly undesirable, particularly interactive sessions with a live user typing at a terminal. The fundamental approach of the present invention is to provide the packet assembler for which the decision to forward a packet is made based on dynamically changing criteria. The criteria established by detection of what are referred in this specification as latency indicators. A latency indicator is a signal condition within the communications network which has been found, through recent past experience, to indicate that a latency delay is likely to be the next event which follows in this particular communications path.
It is a further object of this invention to use information from prior data transfers to predict and avoid latency delays.